Currently, a variety of file system structures exist in the computing environment. One such file system structure is the B-tree file system (BTRFS), which is a GPL-licensed copy-on-write (COW) file system for Linux™. In a BRTFS, everything in the file system, such as inodes, file data, directory entries, and so on, is an ‘item’ in a COW B+tree. BTRFS is structured as several layers of trees, all using the same b-tree implementation to store their various data types as generic ‘items’ sorted on a ‘key’ that specifies an object id and an item type, so that BTRFS is data agnostic. An ‘item’ is a data structure used in BTRFS which includes a combination of a ‘key’ data structure (where to find the item itself), a type of the item, and an offset where the data referenced by the item can be found. ‘Items’ are packed together (or pushed out to leaves) in arrangements that optimize both access time and disk space. In most cases in BTRFS, ‘items’ for the same object end up adjacent to each other in the tree, ordered by type.
Moreover, BTRFS provides extent-based file storage. An extent is a contiguous area of storage. In BTRFS, extents are zoned into block groups, which default to 4 KB in size and contain only file data. Each node and leaf of the BTRFS is an extent in the b-tree. Nodes are extents full of <key, block header> pairs, and leaves contain ‘items’. The extents for large file data are kept outside the BTRFS b-tree, with an extent ‘item’ in the leaf describing the extent where the large file data is kept. Small files that occupy less than one leaf block may be packed into the b-tree itself, inside of the extent ‘item.’
An extent allocation tree (also called an extent tree) is used to track space usage by extents and manage allocated space on the extent trees in the BTRFS. The space available can be divided between a number of extent trees and reduce lock contention and give different allocation policies to different block ranges.
When mounting a file system, such as a BTRFS, a free space cache is typically generated in memory to keep track of the free space available in the file system. When an application running on the computer system needs disk space, it requests a region of specified size from the file system included in the computer system. The file system manages unallocated storage space, and may use a data structure stored in primary memory (e.g., random access memory (RAM)) to determine what storage space to allocate to the application to satisfy the request. Various data structure may be used to represent the free space available in the file system. For instance, an extent may be used to represent the offset and the length of free space available in a block group. Additionally, a bitmap may also be used, which utilizes bits to represent whether particular page blocks are free or not.
However, in typical file systems, generating such a free space data structure in memory is a very intensive process. Typically, to generate a free space cache, the extent allocation tree is referenced to determine what is free in each block group of the file system. To do this, the extent allocation tree must be walked to read all of the extent block groups and determine what space is free in the block group. This means that many blocks (e.g., in the order of thousands) in the memory structure need to be searched, which can be time-consuming and inefficient, resulting in performance slowdowns.